package com.lw.leetcode.linked.b;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 带待优化
 * 6157. 二进制字符串重新安排顺序需要的时间
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/21 17:34
 */
public class SecondsToRemoveOccurrences {

    public static void main(String[] args) {
        SecondsToRemoveOccurrences test = new SecondsToRemoveOccurrences();

        // 4
//        String str = "0110101";

        // 0
//        String str = "11100";

        String str = Utils.getStr(100, '0', '1');

        int i = test.secondsToRemoveOccurrences(str);
        System.out.println(i);
    }

    public int secondsToRemoveOccurrences(String s) {
        char[] arr = s.toCharArray();
        int length = s.length();
        Node st = new Node(-1);
        Node end = new Node(-1);
        st.next = end;
        end.pre = st;
        Node item = st;
        for (int i = 1; i < length; i++) {
            if (arr[i] == '1' && arr[i - 1] == '0') {
                add(item, i);
                item = item.next;
            }
        }
        int c = 0;
        while (st.next.index != -1) {
            item = end.pre;
            while (item.index != -1) {
                int index = item.index;
                arr[index - 1] = '1';
                arr[index] = '0';
                if (index + 1 != length && arr[index + 1] == '1') {
                    add(item, index + 1);
                }
                item = item.pre;
                if (index - 1 != 0 && arr[index - 2] != '1') {
                    item.next.index = index - 1;
                } else {
                    sub(item);
                }
            }
            c++;
        }
        return c;
    }

    private void sub(Node pre) {
        Node item = pre.next;
        Node next = item.next;
        pre.next = next;
        next.pre = pre;
        item.next = null;
        item.pre = null;
    }

    private void add(Node item, int i) {
        Node node = new Node(i);
        Node next = item.next;
        item.next = node;
        node.pre = item;
        node.next = next;
        next.pre = node;
    }

    private static class Node {
        private Node pre;
        private Node next;
        private int index;

        public Node(int index) {
            this.index = index;
        }
    }


    /**
     * 网友解题，牛逼的思路
     *
     * @param s
     * @return
     */
    public int secondsToRemoveOccurrences2(String s) {
        char[] arr = s.toCharArray();

        int res = 0;
        int cnt = 0;
        for (char c : arr) {
            if (c == '0') {
                ++cnt;
            } else if (cnt > 0) {
                res = Math.max(res + 1, cnt);
            }
        }
        return res;
    }
}
